package com.LeeCode;

/**
 * 不同路径 III
 */

public class Code980 {
    public static void main(String[] args) {
        int[][] grid = {
                {1, 0, 0, 0},
                {0, 0, 0, 0},
                {0, 0, 2, -1}
        };
        System.out.println(new Code980().uniquePathsIII(grid));
    }

    private int ans = 0;
    private int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public int uniquePathsIII(int[][] grid) {
        int[] start = new int[2], end = new int[2];
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    start[0] = i;
                    start[1] = j;
                } else if (grid[i][j] == 2) {
                    end[0] = i;
                    end[1] = j;
                } else if (grid[i][j] == 0) {
                    count++;
                }
            }
        }

        backtrace(start, end, grid, count);
        return ans;
    }

    private void backtrace(int[] cur, int[] end, int[][] grid, int count) {
        if (cur[0] == end[0] && cur[1] == end[1]) {
            if (count == -1) ans++;
            return;
        }

        int[] next = new int[2];
        for (int[] direction : directions) {
            next[0] = cur[0] + direction[0];
            next[1] = cur[1] + direction[1];
            if (next[0] >= 0 && next[0] < grid.length && next[1] >= 0 && next[1] < grid[0].length
                    && (grid[next[0]][next[1]] == 0 || grid[next[0]][next[1]] == 2)) {
                int temp = grid[next[0]][next[1]];
                grid[next[0]][next[1]] = -1;
                backtrace(next, end, grid, count - 1);
                grid[next[0]][next[1]] = temp;
            }
        }
    }
}
